import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 56. 合并区间
 * https://leetcode-cn.com/problems/merge-intervals/
 */
public class Solutions_56 {
    public static void main(String[] args) {
//        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
//         output: {{1, 6}, {8, 10}, {15, 18}}
        int[][] intervals = {{1, 4}, {4, 5}};  // output: {{1, 5}}

        int[][] result = merge(intervals);
        System.out.println(Arrays.deepToString(result));
    }

    /**
     * 1. 对开始区间进行升序排列
     * 2. 定义 left，right 变量记录合并后区间的左右索引
     * 3. 若下一区间的左指针小于等于 right 指针，那么进行合并，即取 right 的最大值
     *      Math.max(right, intervals[0][1]);
     */
    public static int[][] merge(int[][] intervals) {
        // 区间数量不足 2 时，无法合并
        if (intervals.length < 2) {
            return intervals;
        }
        // 排序规则：对开始区间进行升序排列
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        List<int[]> res = new ArrayList<>();
        // 排序过，所以不会出现后面的区间左侧元素小于前面的区间左侧元素
        int left = intervals[0][0], right = intervals[0][1];
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                // 与记录的 [left, right] 区间不重叠时，将记录的区间加入结果集
                res.add(new int[]{left, right});
                // 当前区间成为新的 [left, right] 区间
                left = interval[0];
                right = interval[1];
            } else {
                // 右侧取最大值
                right = Math.max(right, interval[1]);
            }
        }
        // 不要忽略最后一个区间数组
        res.add(new int[]{left, right});
        return res.toArray(new int[res.size()][]);
    }
}
